package leetcode.code0773;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	// 四方遍历数组，{左，右，上，下}
	static int[] d = new int[] { 0, -1, 0, 1, -1, 0, 1, 0 };

	int limit = 0b111111111111111111;

	int one = 0b111;

	static List<Integer>[] ways;

	static {
		ways = new ArrayList[6];
		for (int i = 0; i < 6; i++) {
			ways[i] = new ArrayList<>();
		}
		for (int x = 0; x < 2; x++) {
			for (int y = 0; y < 3; y++) {
				int index = index(x, y);
				for (int i = 0; i < 8; i += 2) {
					int nextx = x + d[i], nexty = y + d[i + 1];
					if (nextx >= 0 && nextx < 2 && nexty >= 0 && nexty < 3) {
						int nextIndex = index(nextx, nexty);
						ways[index].add(nextIndex);
					}
				}
			}
		}
	}

	public int slidingPuzzle(int[][] board) {
		int init = this.hash(board);
		int pos0 = this.pos0(board);
		Map<Integer, Integer> times = new HashMap<>();
		times.put(init, 0);
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { pos0, init });
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int pos = cur[0], status = cur[1];
			if (status == 0b1010011100101000) {
				return times.get(status);
			}
			int nextTime = times.get(status) + 1;
			Map<Integer, Integer> nextStatuses = this.nexts(pos, status, ways);
			for (Map.Entry<Integer, Integer> entry : nextStatuses.entrySet()) {
				int nextStatus = entry.getKey(), nextPos = entry.getValue();
				if (!times.containsKey(nextStatus)) {
					times.put(nextStatus, nextTime);
					queue.add(new int[] { nextPos, nextStatus });
				}
			}
		}
		return -1;
	}

	// 在status状态下，从零在pos位置，到下一个位置的可能集合。
	private Map<Integer, Integer> nexts(int pos, int status, List<Integer>[] ways) {
		List<Integer> way = ways[pos];
		Map<Integer, Integer> ans = new HashMap<>();
		for (Integer next : way) {
			int nextStatus = this.swap(status, pos, next);
			ans.put(nextStatus, next);
		}
		return ans;
	}

	private int swap(int status, int a, Integer b) {
		int numa = this.pick(status, a);
		int numb = this.pick(status, b);
		status = this.clear(status, a, b);
		status = this.add(status, b, numa);
		status = this.add(status, a, numb);
		return status;
	}

	// status的a段加上muna状态。段从左到右依次是0，1，2，3，4，5，每一段是三位
	private int add(int status, int a, int numa) {
		return status | (numa << move(a));
	}

	// 将status的，a，b段清空为000
	private int clear(int status, int a, Integer b) {
		status = status & ((limit << (move(a) + 3)) | ((1 << (move(a))) - 1));
		status = status & ((limit << (move(b) + 3)) | ((1 << (move(b))) - 1));
		return status;
	}

	// 第pos段向左移动的步数
	private int move(int pos) {
		int ans = (5 - pos) * 3;
		return ans;
	}

	// 摘出status的pos段内容
	private int pick(int status, int pos) {
		int num = (one << move(pos)) & status;
		return num >> move(pos);
	}

	// 按照位置组织转移路径集合
	public List<Integer>[] ways() {
		List<Integer>[] ans = new ArrayList[6];
		for (int i = 0; i < 6; i++) {
			ans[i] = new ArrayList<>();
		}
		for (int x = 0; x < 2; x++) {
			for (int y = 0; y < 3; y++) {
				int index = Solution.index(x, y);
				for (int i = 0; i < 8; i += 2) {
					int nextx = x + d[i], nexty = y + d[i + 1];
					if (nextx >= 0 && nextx < 2 && nexty >= 0 && nexty < 3) {
						int nextIndex = Solution.index(nextx, nexty);
						ans[index].add(nextIndex);
					}
				}
			}
		}
		return ans;
	}

	// 0的位置
	private int pos0(int[][] board) {
		int m = board.length, n = board[0].length;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (board[i][j] == 0) {
					return Solution.index(i, j);
				}
			}
		}
		return 0;
	}

	// 二维转一维
	public static int index(int x, int y) {
		return x * 3 + y;
	}

	// 把数组变成一个hash状态
	public int hash(int[][] borard) {
		int ans = 0;
		int m = borard.length, n = borard[0].length;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				int cur = borard[i][j];
				ans <<= 3;
				ans |= cur;
			}
		}
		return ans;
	}

	@Override
	public void debug4() {
		HelpDebug.compare(1, this.slidingPuzzle(HelpDebug.str2array1("[[1,2,3],[4,0,5]]")));
		HelpDebug.compare(-1, this.slidingPuzzle(HelpDebug.str2array1("[[1,2,3],[5,4,0]]")));
		HelpDebug.compare(5, this.slidingPuzzle(HelpDebug.str2array1("[[4,1,2],[5,0,3]]")));
		HelpDebug.compare(14, this.slidingPuzzle(HelpDebug.str2array1("[[3,2,4],[1,5,0]]")));
//		this.slidingPuzzle(H.str2array1("[[1,2,3],[4,5,0]]"));
//		int hash = this.hash(H.str2array1("[[1,2,3],[4,5,0]]"));
//		System.out.println(Integer.toBinaryString(hash));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
